package ChainTable;

public class DoubleLink {
    //双链表
    private int size;
    //头节点
    private DoubleNode head;
    //尾节点
    private DoubleNode tail;

    public void addFirst(int val) {
        DoubleNode node = new DoubleNode(null, val, head);
        if (head == null) {
            tail = node;
        } else {
            //让头结点的前驱指向新建节点
            head.prev = node;
        }
        //头节点变为最新节点
        head = node;
        size++;
    }

    public void addLast(int val) {
        DoubleNode node = new DoubleNode(tail, val, null);
        if (tail == null) {
            head = node;
        } else {
            //让尾节点后继指向新建节点
            tail.next = node;
        }
        //更新尾节点
        tail = node;
        size++;
    }

    /**
     * 根据索引在链表中插入节点
     *
     * @param index
     * @param val
     */
    public void addIndex(int index, int val) {
        if (index < 0 || index > size) {
            System.out.println("add index illegal!");
            return;
        } else if (index == 0) {
            addFirst(val);
        } else if (index == size) {
            addLast(val);
        } else {
            DoubleNode prev = node(index - 1);
            DoubleNode newNode = new DoubleNode(prev, val, prev.next);
            prev.next.prev = newNode;
            prev.next = newNode;
            size++;
        }
    }

    /**
     * 根据索引查找元素
     *
     * @param index
     * @return 输出索引节点值
     */
    public int get(int index) {
        //检查index合法性
        if (rangeIndex(index)) {
            //调用查找索引节点方法输出节点值
            return node(index).val;
        } else {
            System.out.println("set index illegal!");
            return -1;
        }
    }

    public boolean contains(int val) {
        for (DoubleNode x = head; x != null; x = x.next) {
            if (x.val == val) {
                return true;
            }
        }
        return false;
    }

    private boolean rangeIndex(int index) {
        if (index < 0 || index >= size) {
            return false;
        }
        return true;
    }

    public int set(int index, int newVal) {
        if (rangeIndex(index)) {
            DoubleNode node = node(index);
            int oldVal = node.val;
            node.val = newVal;
            return oldVal;
        } else {
            System.out.println("set index illegal!");
            return -1;
        }
    }

    /**
     * 根据索引删除节点
     *
     * @param index
     */
    public void removeIndex(int index) {
        if (rangeIndex(index)) {
            DoubleNode node = node(index);
            unlink(node);
        } else {
            System.out.println("remove index illegal!");
        }
    }

    public void removeFirst() {
        removeIndex(0);
    }

    public void removeLast() {
        removeIndex(size - 1);
    }

    /**
     * 删除第一个值为val的节点
     *
     * @param val
     */
    public void removeVlaOnce(int val) {
        for (DoubleNode node = head; node != null; node = node.next) {
            if (node.val == val) {
                unlink(node);
                break;
            }
        }
    }

    /**
     * 删除链表中所有值为val的节点
     *
     * @param val
     */
    public void removeValAll(int val) {
        DoubleNode node = head;
        while (node != null) {
            if (node.val == val) {
                //node是待删除节点
                //创建next暂时保存node的下一节点
                DoubleNode next = node.next;
                unlink(node);//此时node.next，node.prev均指向空
                //node指向next
                node = next;
            } else {
                //node不是待删除结点，node移到下一节点
                node = node.next;
            }
        }
    }

    /**
     * 在双链表中删除节点
     *
     * @param node
     */
    private void unlink(DoubleNode node) {
        //分之思想
        DoubleNode prev = node.prev;
        DoubleNode next = node.next;
        if (prev == null) {
            head = next;
        } else {
            //有前驱
            prev.next = next;
            node.next = null;
        }
        if (next == null) {
            tail = prev;
        } else {
            //有后继
            next.prev = prev;
            node.prev = null;
        }
        size--;
    }

    /**
     * 打印链表
     *
     * @return ret从头结点输出
     */
    public String toString() {
        String ret = "";
        DoubleNode node = head;
        while (node != null) {
            ret += node.val + "->";
            node = node.next;
        }
        ret += "Null";
        return ret;
    }

    /**
     * 找到index索引对应的节点
     *
     * @param index
     * @return index对应的节点
     */
    private DoubleNode node(int index) {
        DoubleNode ret = null;
        //如果索引小于链表一半从头结点开始查找
        if (index < size >> 1) {
            ret = head;
            for (int i = 0; i < index; i++) {
                ret = ret.next;
            }
        } else {
            //索引大于链表一半
            ret = tail;
            for (int i = size - 1; i > index; i--) {
                ret = ret.prev;
            }
        }
        return ret;
    }
}

class DoubleNode {
    DoubleNode prev;
    int val;
    DoubleNode next;

    public DoubleNode(DoubleNode prev, int val, DoubleNode next) {
        this.prev = prev;
        this.val = val;
        this.next = next;
    }

    public DoubleNode(int val) {
        this.val = val;
    }
}